class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int ans = 0;
        vector<unordered_map<long long, int>> dp(nums.size());
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                long long d = (long long)nums[i] - nums[j];
                int temp = 0;
                if(dp[j].find(d) != dp[j].end())temp = dp[j];
                ans += temp;
                dp[i][d] += temp + 1;
            }
        }
    }
};

//2021.9.11
//dp[i][d]代表尾项为 nums[i], 公差为 d 的等差数列子序列数目
//若 nums[i] - nums[j] = d 则有状态转移方程 dp[i][d] += d[j][d] + 1; 
//dp[j][d]的存在表示 nums[j] nums[j] - d 可以构成至少两个数的公差为 d 的“弱等差子序列”
//再加上 nums[i],此时已经至少存在 3 个数了，加到 ans 上面去。